package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 230. 二叉搜索树中第K小的元素
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/17 11:36
 */
public class KthSmallest {
    public int kthSmallest(TreeNode root, int k) {

        int i = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        TreeNode item = root.left;
        while (!stack.isEmpty() || item != null) {
            if (item == null) {
                item = stack.pop();
                i++;
                if (k == i) {
                    return item.val;
                }
                item = item.right;
            } else {
                if (item.left != null) {
                    stack.add(item);
                    item = item.left;
                } else {
                    i++;
                    if (k == i) {
                        return item.val;
                    }
                    item = item.right;
                }
            }
        }
        return 0;
    }
}
